package chapter8;

/**
 * 线性时间排序-计数排序
 * <p>
 * 非原址排序-最坏/平均O(n)
 */
public class CountingSort {

    /**
     * 对于原数组的每个元素计算小于或等于自身的数量来确定位置
     *
     * @param A
     * @param B
     * @param k
     */
    public static void countingSort(int[] A, int[] B, int k) {
        // 扩充k个槽位
        int[] C = new int[k + 1];
        // 给每个槽计数
        for (int i = 0; i < A.length; i++) {
            C[A[i]] += 1;
        }
        // 累计比当前槽位小于等于的数量,也就是在最终数组中排列的位置
        for (int i = 1; i <= k; i++) {
            C[i] += C[i - 1];
        }
        // 按位置输出
        for (int i = A.length - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]]--;
        }
    }

}
